//<p>给你一个字符串数组，请你将 <strong>字母异位词</strong> 组合在一起。可以按任意顺序返回结果列表。</p>
//
//<p><strong>字母异位词</strong> 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1:</strong></p>
//
//<pre>
//<strong>输入:</strong> strs = <code>["eat", "tea", "tan", "ate", "nat", "bat"]</code>
//<strong>输出: </strong>[["bat"],["nat","tan"],["ate","eat","tea"]]</pre>
//
//<p><strong>示例 2:</strong></p>
//
//<pre>
//<strong>输入:</strong> strs = <code>[""]</code>
//<strong>输出: </strong>[[""]]
//</pre>
//
//<p><strong>示例 3:</strong></p>
//
//<pre>
//<strong>输入:</strong> strs = <code>["a"]</code>
//<strong>输出: </strong>[["a"]]</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 &lt;= strs.length &lt;= 10<sup>4</sup></code></li>
//	<li><code>0 &lt;= strs[i].length &lt;= 100</code></li>
//	<li><code>strs[i]</code>&nbsp;仅包含小写字母</li>
//</ul>
//<div><div>Related Topics</div><div><li>哈希表</li><li>字符串</li><li>排序</li></div></div><br><div><li>👍 1134</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import cn.hutool.json.JSONUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 字母异位词分组
 * @author DY Rising
 * @date 2022-05-12 20:09:12
 */
public class P49_GroupAnagrams{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P49_GroupAnagrams().new Solution();
        //System.out.println(JSONUtil.toJsonStr(solution.groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"})));
        System.out.println(JSONUtil.toJsonStr(solution.groupAnagrams(new String[]{"","b",""})));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> rtns = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        /*for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            if (map.get(new String(chars)) == null) {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(new String(chars), list);
            } else {
                map.get(new String(chars)).add(strs[i]);
            }
        }
        rtns.addAll(map.values());*/
        if (strs.length == 1) {
            List<String> list = new ArrayList<>();
            list.add(strs[0]);
            rtns.add(list);
        } else {
            dfs(0, strs.length - 1, strs, map);
            rtns.addAll(map.values());
        }
        return rtns;
    }

    public void dfs(int left, int right, String[] strs, Map<String, List<String>> map) {
        if (left > right) {
            return;
        }
        add(left, strs, map);
        if (left != right) add(right, strs, map);
        int mid = (left + right) >> 1;
        dfs(left + 1, mid, strs, map);
        dfs(mid + 1, right - 1, strs, map);
    }

    public void add(int index, String[] strs, Map<String, List<String>> map) {
        char[] chars = strs[index].toCharArray();
        Arrays.sort(chars);
        if (map.get(new String(chars)) == null) {
            List<String> list = new ArrayList<>();
            list.add(strs[index]);
            map.put(new String(chars), list);
        } else {
            map.get(new String(chars)).add(strs[index]);
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
